package com.lihepeng.leecode.array2;

/**
 * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
 *
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 返回容器可以储存的最大水量。
 *
 * 说明：你不能倾斜容器。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/container-with-most-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @see Solution42
 */
public class Solution11 {
    // 可以使用枚举的方案 来实现 时间复杂度很高

    /**
     * 使用两个指针  ，逐渐向中间进行收敛  如果 碰到 高度更大的话，计算面积
     *  两边同时向中间进行夹逼 的方案来实现的
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length-1;
        int max = 0;
        while (i<j) {
            int minHeigth = height[i]<height[j] ?height[i++] : height[j--];
            int area = (j-i+1)*minHeigth;
            max = Math.max(area,max);
        }
        return max;
    }

    /**
     * 使用双指针来实现
     * 两个指针分别指向 数组的开始和结尾的数组逐渐向中间 移动
     * 根据  面积min（heigh[i],heigh[j]）* j-i+1  克制如果高度
     * 小的话，移动该指针，同时更新面积的值，知道两个指针相遇
     * @param height
     * @return
     */
    public int maxArea01(int[] height) {
        int i = 0;
        int j = height.length -1;
        int area = 0;
        while (i < j) {
            int minHeigh = Math.min(height[j],height[i]);
            area = Math.max((j-i) * minHeigh,area);
            if (height[j]>height[i]) {
                i++;
            }else {
                j--;
            }
        }
        return area;
    }

}
